//
// Created by Administrator on 2021/11/14.
//
#include <cstdio>
#include <cstdlib>

#define MaxSize 100//定义最大个数
#define ElemType int
/*二叉排序树结点*/
typedef struct BSTNode {
    int key;
    struct BSTNode *lchild, *rchild;
} BSTNode, *BSTree;

/*在二叉排序树中查找值为key的结点*/
BSTNode *BST_Search(BSTree T, int key) {
    while (T != NULL && key != T->key) {
        //若树空或等于根结点值，则结束循环
        if (key < T->key) {
            T = T->lchild;//小于，则在左子树上查找
        } else {
            T = T->rchild;//大于，则在右子树上查找
        }
    }
    return T;
}

/*在二叉排序树中查找值为key 的结点（递归实现)*/
BSTNode *BSTSearch(BSTree T, int key) {
    if (T == NULL) {
        return NULL;//查找失败
    }
    if (key == T->key) {
        return T;//查找成功
    } else if (key < T->key) {
        return BSTSearch(T->lchild, key);//在左子树中找
    } else {
        return BSTSearch(T->rchild, key);//在右子树中找
    }
}

/*在二叉排序树插入关键字为k的新结点（递归实现)*/
int BST_Insert(BSTree &T, int k) {
    if (T == NULL) {
        //原树为空，新插入的结点为根结点
        T = (BSTree) malloc(sizeof(BSTNode));
        T->key = k;
        T->lchild = T->rchild = NULL;
        return 1;//返回1，插入成功
    } else if (k == T->key) {
        return 0;//树中存在相同关键字的结点，插入失败
    } else if (k < T->key) {
        return BST_Insert(T->lchild, k);//插入到T的左子树
    } else {
        return BST_Insert(T->rchild, k);//插入到T的右子树
    }
}

/*按照str[]中的关键字序列建立二叉排序树*/
void Creat_BST(BSTree &T, int str[], int n) {
    T = NULL;//初始时T为空树
    int i = 0;
    while (i < n) {
        //依次将每个关键字插入到二叉排序
        BST_Insert(T, str[i]);
        i++;
    }
}

/*二叉排序树的删除：
 * 先搜索找到目标结点:
 * ①若被删除结点z是叶结点，则直接删除，不会破坏二叉排序树的性质。
 * ②若结点z只有一棵左子树或右子树，则让z的子树成为z父结点的子树，替代z的位置。
 * ③若结点z有左、右两棵子树，则令z的直接后继（或直接前驱）替代z，然后从二叉排序树中删去这个直接后继（或直接前驱），这样就转换成了第一或第二种情况。
 * z的后继:z的右子树中最左下结点(该节点没有左子树)
 * z的前驱:z的左子树中最右下结点（该节点设有右子树)
*/
/*查找长度――在查找运算中，需要对比关键字的次数称为查找长度，反映了查找操作时间复杂度
 * 查找成功的平均查找长度ASL (Average Search Length)
 * （示例）ASL = (1*1＋2*2+3*4+4*1)/8= 2.625【（第n层（对比次数）*个数）/总个数】
 *
 * 查找失败的平均查找长度ASL (Average Search Length)
 * （示例）ASL = (3*7＋4*2)/9 =3.22【（第n层（对比次数）*null的结点个数）/null的结点总数】
*/

/*平衡二叉树结点*/
typedef struct AVLNode {
    int key;//数据域
    int balance;//平衡因子
    struct AVLNode *lchild, *rchild;
} lAVLNode, *AVLTree;

/*右旋
 * 实现f 向右下旋转，p向右上旋转:其中 f是参，p为左孩子，gf为f他爹
 * ① f->lchild = p->rchild;（=是指向的意思，不是赋值）
 * ② p->rchild = f;
 * ③ gf->Ichild/rchild = p;
 * */
/*左旋
 * 实现f向左下旋转，p向左上旋转:其中f是参，p为右孩子，gf为f他爹
 * ① f->rchild = p->lchild;
 * ② p->lchild = f;
 * ③ gf->lchild/rchild = p;
 * */
/*只有右孩子才能左旋
 * 只有左孩子才能右旋*/
/*假设以n(h)表示深度为h的平衡树中含有的最少结点数
 * 前三位0/1/2
 * n(h)=n(h-1)+n(h-2)+1
 * 画图：从下往上画，保证每一个子树都是最小平衡二叉树
*/